package clue;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Set;

import clue.cards.Card;
import clue.cards.RoomCard;
import clue.cards.SuspectCard;
import clue.cards.WeaponCard;
import clue.engine.Deck;
import clue.enums.Room;
import clue.enums.Suspect;
import clue.enums.Weapon;
import clue.util.Utilities;

public class EnumerationEngine2 {
	private final int numOpponents;
	public final long ourHand;
	private final int ourHandSize;
	private final int[] oppHandSizes;
	
	//
	// tally[0] -> in opp 0's hand
	// tally[1] -> in opp 1's hand
	// ...
	// tally[numOpponents] -> in env
	//
	private final int[][] tally;
	private final double[][] prob;
	
	//
	// accessed by [WeaponIdx][SuspectIdx][RoomIdx]
	//
	private final int[][][] envBuckets;
	public final double[][][] envProb;
	
	public final List<Particle> particles;
	
	public double entropy;
	
	public double[][][][][] reactionEntropies;

	public EnumerationEngine2(int numPlayers, Card[] ourCards) {
		this.numOpponents = numPlayers - 1;
		this.ourHand = convertCardsToLong(ourCards);
		this.ourHandSize = ourCards.length;
		this.oppHandSizes = new int[numOpponents];
		for (int i = 0; i < (18 - ourHandSize); i++) {
			oppHandSizes[i % numOpponents]++;
		}
		tally = new int[numOpponents + 1][21];
		prob = new double[numOpponents + 1][21];
		envBuckets = new int[6][6][9];
		envProb = new double[6][6][9];
		particles = new LinkedList<Particle>();
		reactionEntropies = new double[9][6][6][21][numOpponents];
		ourHand();
	}

	public double getProb(Card c, int idx) {
		return prob[idx][convertCardToIdx(c)];
	}

	private void undoTemp(Set<Particle> temp) {
		for (Particle p : temp)
			p.incrementTally();
		
		updateTallyProb();
		updateEnvProb();
	}
	
	private Set<Particle> mustExistTemp(long l, int opp, Set<Particle> temp) {
		// if not exist
		ListIterator<Particle> li = particles.listIterator();
		Set<Particle> ret = new HashSet<>();
		while (li.hasNext()) {
			Particle particle = li.next();
			if (!particle.exists(l, opp)) {
				if (!temp.contains(particle)) {
					particle.decrementTally();
					ret.add(particle);
				}
			}
		}

		updateTallyProb();
		updateEnvProb();
		return ret;
	}
	
	public void mustExist(Card c, int opp) {
		long l = convertCardToLong(c);

		// if not exist
		ListIterator<Particle> li = particles.listIterator();
		while (li.hasNext()) {
			Particle particle = li.next();
			if (!particle.exists(l, opp)) {
				particle.decrementTally();
				li.remove();
			}
		}

		updateTallyProb();
		updateEnvProb();
	}
	
	public void mustNotExistTemp(long l, int opp, Set<Particle> temp) {
		// if exist
		ListIterator<Particle> li = particles.listIterator();
		Set<Particle> ret = new HashSet<>();
		while (li.hasNext()) {
			Particle particle = li.next();
			if (particle.exists(l, opp)) {
				if (!temp.contains(particle)) {
					particle.decrementTally();
					temp.add(particle);
				}
			}
		}

		updateTallyProb();
		updateEnvProb();
	}
	
	public void mustNotExist(Card[] c, int opp) {
		long l = convertCardsToLong(c);

		// if exist
		ListIterator<Particle> li = particles.listIterator();
		while (li.hasNext()) {
			Particle particle = li.next();
			if (particle.exists(l, opp)) {
				particle.decrementTally();
				li.remove();
			}
		}

		updateTallyProb();
		updateEnvProb();
	}
		
	//
	// This reflects what the other two opponents do to each other
	// <opp> made a suggestion containing <cards>
	// if <refuted>, then other opponent must have one of the cards
	// else, then other opponent must not have any of the cards
	//
	public void opponentReaction(Card[] cards, int reactingOpp, boolean refuted) {
		long suggestion = convertCardsToLong(cards);

		ListIterator<Particle> li = particles.listIterator();
		while (li.hasNext()) {
			Particle particle = li.next();

			if ((refuted && !particle.exists(suggestion, reactingOpp))
					|| (!refuted && particle.exists(suggestion, reactingOpp))) {
				// if other opponent refuted, which means other opponent must
				// have at least *one* of the suggestion cards.
				//
				// if other opponent did not refute, which means other opponent
				// does not have *any* of the suggestion cards.
				particle.decrementTally();
				li.remove();
			}
		}

		updateTallyProb();
		updateEnvProb();
	}
	
	public void calculateReactions() {
		// Suggestions go around until one guy refutes it with one card.
		// get the set of cards not in our hand
		reactionEntropies = new double[9][6][6][21][numOpponents];
		for (int r = 0; r < 9; r++) {
			long rl = 1l << (r + 12);
			if ((rl & ourHand) != 0)
				continue;
			for (int s = 0; s < 6; s++) {
				long sl = 1l << (s + 6);
				if ((sl & ourHand) != 0)
					continue;
				for (int w = 0; w < 6; w++) {
					long wl = 1l << w;
					if ((wl & ourHand) != 0)
						continue;
					long suggestion = rl | sl | wl;
					for (int j = 0; j < numOpponents; j++) {
						Set<Particle> set = new HashSet<Particle>();
						for (int k = 0; k < j; k++) {
							mustNotExistTemp(suggestion, k, set);
						}
						Set<Particle> extra = mustExistTemp(rl, j, set);
						reactionEntropies[r][s][w][r+12][j] = entropy;
						undoTemp(extra);
						extra = mustExistTemp(sl, j, set);
						reactionEntropies[r][s][w][s+6][j] = entropy;
						undoTemp(extra);
						extra = mustExistTemp(wl, j, set);
						reactionEntropies[r][s][w][w][j] = entropy;
						undoTemp(extra);
						undoTemp(set);
					}
				}
			}
		}
	}
	
	private void ourHand() {
		for (long w = 1l; w < (1l << 6); w <<= 1) {
			// if it's in our hand, skip it
			if ((ourHand & w) != 0)
				continue;

			for (long s = (1l << 6); s < (1l << 12); s <<= 1) {
				if ((ourHand & s) != 0)
					continue;

				for (long r = (1l << 12); r < (1l << 21); r <<= 1) {
					if ((ourHand & r) != 0)
						continue;

					long remaining = ~(ourHand | w | s | r) & 0x1FFFFF;
					int particlesSize = particles.size();
					enumerateOppHands(remaining, w | s | r);
					particlesSize = particles.size() - particlesSize;
					envBuckets[convertLongToEnumIdx(w)][convertLongToEnumIdx(s)][convertLongToEnumIdx(r)] += particlesSize;
				}
			}
		}

		updateTallyProb();
		updateEnvProb();
	}
	
	private void updateTallyProb() {
		for (int i = 0; i < 21; i++) {
			int sum = 0;
			for (int j = 0; j < tally.length; j++)
				sum += tally[j][i];
			if (sum == 0)
				continue;

			for (int j = 0; j < tally.length; j++)
				prob[j][i] = ((double) tally[j][i]) / sum;
		}
	}
	
	private void updateEnvProb() {
		int count = 0;
		entropy = 0;
		for (int w = 0; w < 6; w++)
			for (int s = 0; s < 6; s++)
				for (int r = 0; r < 9; r++) {
					count++;
					envProb[w][s][r] = ((double)envBuckets[w][s][r]) / particles.size();
					if (envProb[w][s][r] > 0)
						entropy += -(envProb[w][s][r] * Math.log(envProb[w][s][r]));
				}
		assert(count == particles.size());
	}
	
	//
	// Enumerates opponent hands
	//
	private void enumerateOppHands(long remaining, long env) {
		// first convert <remaining> to an array of bit positions.
		ArrayList<Integer> list = new ArrayList<Integer>();
		int pos = 0;
		for (long v = 1l; v < (1l << 21); v <<= 1, pos++)
			if ((remaining & v) != 0) 
				list.add(pos);
		
		recursiveChoose(list, oppHandSizes[0], 0, new int[oppHandSizes[0]], 0, new ArrayList<Long>(), remaining, env);
	}
	
	private void recursiveChoose(ArrayList<Integer> positions, 
								 int k, 
								 int startIdx, 
								 int[] result, 
								 int oppIdx, 
								 ArrayList<Long> oppHands,
								 long remaining,
								 long env) {
		if (k == 0) {
			long oppHand = 0;
			int[] map = new int[21];
			for (int i = 0; i < result.length; i++) {
				oppHand ^= 1l << positions.get(result[i]);
				map[result[i]] = 1;
			}
			oppHands.add(oppHand);
			
			if (++oppIdx < numOpponents - 1) {
				ArrayList<Integer> remainingPos = new ArrayList<Integer>();
				for (int i = 0; i < positions.size(); i++)
					if (map[i] != 1) 
						remainingPos.add(positions.get(i));
				recursiveChoose(remainingPos, oppHandSizes[oppIdx], 0, new int[oppHandSizes[oppIdx]], oppIdx, oppHands, remaining, env);
			} else {
				// calculate the last opponent's hand
				long lastHand = 0;
				for (int i = 0; i < oppHands.size(); i++)
					lastHand ^= oppHands.get(i);
				
				lastHand ^= remaining;
				oppHands.add(lastHand);
				particles.add(new Particle(oppHands, env));
				oppHands.remove(oppHands.size() - 1);
			}
			
			oppHands.remove(oppHands.size() - 1);
		} else {
			for (int i = startIdx; i <= (positions.size() - k); i++) {
				result[k-1] = i;
				recursiveChoose(positions, k - 1, i + 1, result, oppIdx, oppHands, remaining, env);
			}
		}
	}
	
	public class Particle {
		public long[] particle;
		
		public Particle(ArrayList<Long> hands, long env) {
			if (hands.size() <= 2) {
				particle = new long[1];
				int i, shift = 0;
				for (i = 0; i < hands.size(); i++) {
					particle[0] |= hands.get(i) << shift;
					incrementTally(hands.get(i), i);
					shift += 21;
				}
				particle[0] |= env << shift;
				incrementTally(env, i);
			} else {
				particle = new long[2];
				int i, shift = 0;
				for (i = 0; i < 3; i++) {
					particle[0] |= hands.get(i) << shift;
					incrementTally(hands.get(i), i);
					shift += 21;
				}
				shift = 0;
				for (; i < hands.size(); i++) {
					particle[1] |= hands.get(i) << shift;
					incrementTally(hands.get(i), i);
					shift += 21;
				}
				particle[1] |= env << shift;
				incrementTally(env, i);
			}
		}
		
		private void incrementTally(long hand, int tallyIdx) {
		    while (hand != 0) {
		    	long bit = hand & ~(hand - 1);
		    	int pos = Utilities.getBitPosition(bit);
		    	tally[tallyIdx][pos]++;
		    	hand ^= bit;
		    }
		}
		
		private void decrementTally(long hand, int tallyIdx) {
			while (hand != 0) {
				long bit = hand & ~(hand - 1);
				int pos = Utilities.getBitPosition(bit);
				tally[tallyIdx][pos]--;
				hand ^= bit;
			}
		}
		
		private void incrementEnv(long hand, int tallyIdx) {
			int wIdx = -1, sIdx = -1, rIdx = -1;
			while (hand != 0) {
				long bit = hand & ~(hand - 1);
				int pos = Utilities.getBitPosition(bit);
				tally[tallyIdx][pos]--;
				hand ^= bit;
				if (pos < 6) {
					assert(wIdx == -1);
					wIdx = pos;
				} else if (pos < 12) {
					assert(sIdx == -1);
					sIdx = pos - 6;
				} else if (pos < 21) {
					assert(rIdx == -1);
					rIdx = pos - 12;
				}
			}

			envBuckets[wIdx][sIdx][rIdx]++;
		}
		
		private void decrementEnv(long hand, int tallyIdx) {
			int wIdx = -1, sIdx = -1, rIdx = -1;
			while (hand != 0) {
				long bit = hand & ~(hand - 1);
				int pos = Utilities.getBitPosition(bit);
				tally[tallyIdx][pos]--;
				hand ^= bit;
				if (pos < 6) {
					assert(wIdx == -1);
					wIdx = pos;
				} else if (pos < 12) {
					assert(sIdx == -1);
					sIdx = pos - 6;
				} else if (pos < 21) {
					assert(rIdx == -1);
					rIdx = pos - 12;
				}
			}

			envBuckets[wIdx][sIdx][rIdx]--;
		}

		void decrementTally() {
			int i;
			if (numOpponents < 3) {
				for (i = 0; i < numOpponents; i++)
					decrementTally((particle[0] >>> (i * 21)) & 0x1FFFFF, i);
				decrementEnv((particle[0] >>> (i * 21)) & 0x1FFFFF, i);
			} else {
				for (i = 0; i < 3; i++)
					decrementTally((particle[0] >>> (i * 21)) & 0x1FFFFF, i);
				for (; i < numOpponents; i++)
					decrementTally((particle[1] >>> ((i - 3) * 21)) & 0x1FFFFF, i);
				decrementEnv((particle[1] >>> (i * 21)) & 0x1FFFFF, i);
			}
		}
		
		void incrementTally() {
			int i;
			if (numOpponents < 3) {
				for (i = 0; i < numOpponents; i++)
					incrementTally((particle[0] >>> (i * 21)) & 0x1FFFFF, i);
				incrementEnv((particle[0] >>> (i * 21)) & 0x1FFFFF, i);
			} else {
				for (i = 0; i < 3; i++)
					incrementTally((particle[0] >>> (i * 21)) & 0x1FFFFF, i);
				for (; i < numOpponents; i++)
					incrementTally((particle[1] >>> ((i - 3) * 21)) & 0x1FFFFF, i);
				incrementEnv((particle[1] >>> (i * 21)) & 0x1FFFFF, i);
			}
		}
		
		public boolean exists(long l, int opp) {
			if (opp < 3) {
				l <<= (opp * 21);
				return (particle[0] & l) != 0;
			} else {
				l <<= ((opp - 3) * 21);
				return (particle[1] & l) != 0;
			}
		}
		
		boolean existsInEnv(long l) {
			return exists(l, numOpponents);
		}
	}
	
	private int convertCardToIdx(Card c) {
		if (c instanceof WeaponCard) {
			switch (((WeaponCard) c).getWeapon()) {
			case CANDLESTICK:
				return 0;
			case DAGGER:
				return 1;
			case LEAD_PIPE:
				return 2;
			case REVOLVER:
				return 3;
			case ROPE:
				return 4;
			case WRENCH:
				return 5;
			}
		} else if (c instanceof SuspectCard) {
			switch (((SuspectCard) c).getSuspect()) {
			case CM:
				return 6;
			case MP:
				return 7;
			case MS:
				return 8;
			case MW:
				return 9;
			case PP:
				return 10;
			case RG:
				return 11;
			}
		} else if (c instanceof RoomCard) {
			switch (((RoomCard) c).getRoom()) {
			case BALLROOM:
				return 12;
			case BILLARD_ROOM:
				return 13;
			case CONSERVATORY:
				return 14;
			case DINING_ROOM:
				return 15;
			case HALL:
				return 16;
			case KITCHEN:
				return 17;
			case LIBRARY:
				return 18;
			case LOUNGE:
				return 19;
			case STUDY:
				return 20;
			}
		}

		return -1;
	}
	
	private int convertLongToEnumIdx(long v) {
		int pos = Utilities.getBitPosition(v);
	    // 0 <= pos <= 20
	    if (pos < 6)
	      return pos;
	    else if (pos < 12)
	      return pos - 6;
	    else if (pos < 21)
	      return pos - 12;
	    return -1;
	}

	private long convertCardToLong(Card c) {
		return 1l << convertCardToIdx(c);
	}

	private long convertCardsToLong(Card[] cards) {
		long ret = 0;
		for (Card c : cards)
			ret ^= convertCardToLong(c);

		return ret;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		EnumerationEngine2 e = new EnumerationEngine2(3,
				new Card[] { new RoomCard(Room.BALLROOM),
						new RoomCard(Room.HALL), new RoomCard(Room.KITCHEN),
						new RoomCard(Room.LIBRARY),
						new WeaponCard(Weapon.CANDLESTICK),
						new SuspectCard(Suspect.CM) });

		e.mustExist(new SuspectCard(Suspect.MP), 0);
		e.mustExist(new SuspectCard(Suspect.MW), 1);
		e.mustNotExist(new Card[] { new RoomCard(Room.CONSERVATORY),
				new WeaponCard(Weapon.WRENCH), new SuspectCard(Suspect.MS) }, 0);

		e.opponentReaction(
				new Card[] {
						new RoomCard(Room.LOUNGE),
						new WeaponCard(Weapon.LEAD_PIPE),
						new SuspectCard(Suspect.PP) },
				1,
				true);
		System.out.println(e.entropy);
		e.calculateReactions();
		for(int r = 0; r < 9; r++) {
			for (int s = 0; s < 6; s++) {
				for (int w = 0; w < 6; w++) {
					for (int j = 0; j < 2; j++) {
						System.out.printf("(%d,%d,%d,%d) = %f\n", r, s, w, j, e.reactionEntropies[r][s][w][s+6][j]);
					}
				}
			}
		}
		System.out.println(e.entropy);
		/*Deck d = new Deck();
		d.mixCards();
		Card c;
		while ((c = d.removeMixedCard()) != null) {
			for (int i = 0; i < 3; i++) {
				System.out.println(c + ":" + e.getProb(c, i));
			}
		}*/
		
		/*for (int w = 0; w < 6; w++) {
			double wSum = 0;
			for (int s = 0; s < 6; s++)
				for (int r = 0; r < 9; r++)
					if (e.envProb[w][s][r] > 0)
						System.out.printf("w = %s, s = %s, r = %s, prob = %f\n", 
								Weapon.values()[w].name(), 
								Suspect.values()[s].name(), 
								Room.values()[r].name(), 
								wSum +=e.envProb[w][s][r]);
			System.out.printf("w = %s, sumProb = %f\n", Weapon.values()[w].name(), wSum);
		}*/
	}

}
